package com.zhang.eightSorts;

import java.util.Arrays;

/**
 * 快排，基于冒泡
 */
public class QuickSort {
    public static void main(String[] arg0)
    {
        int[] arr={-9,78,0,23,-567,70};
       quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    public static void  quickSort(int[] arr,int left,int right)
    {
        int l=left;//左下标
        int r=right;//右下标
        int privot=arr[(left+right)/2];//获取中间值
        int temp=0;//临时替换
        while (l<r)
        {
            //在中间值左边一直查找，找到大于等于中间值才退出
            while (arr[l]<privot)
            {
                l +=1;
            }
            //在中间值又边一直查找，找到小于等于中间值才退出
            while (arr[r]>privot)
            {
                r -= 1;
            }
//          如果l=r
// 说明中间值的左右两个值以及按照左边都是小于中间值的，
// 右边都是大于中间值的
            if (l>=r)
            {
                break;
            }
            //开始交换
            temp=arr[l];
            arr[l]=arr[r];
            arr[r]=temp;

            //如果交换后发现arr[l]==pivot值 相等
            if(arr[l]==privot)
            {
              r -=1;
            }
            if (arr[r]==privot)
            {
               l +=1;
            }
        }
        //必须做处理不然会导致栈溢出
        if (l==r)
        {
            l+=1;
            r-=1;
        }
        //然后左递归
        if (left<r)
        {
            quickSort(arr,left,r);
        }
        //然后右递归
        if (right>l)
        {
            quickSort(arr,l,right);
        }
    }
}
